type automate = {n : int ; final : bool array ; trans : (int*int) array};;

let aut_1 = {n = 2 ; final = [|true;false|] ; trans = [|(1,0);(0,1)|]};;
let aut_2 = {n = 2 ; final = [|false;true|] ; trans = [|(0,0);(1,0)|]};;

(* Exercice 2 *)

let trad s =
	let liste = ref [] in
	for i = (String.length s)-1 downto 0 do
		liste := (s.[i])::(!liste)
	done;
	!liste;;

trad "hello world";;

(* Exercice 3 *)

let accepte aut mot =
	let etat = ref 0 in
	for i = 0 to (String.length mot)-1 do
		etat := let eta,etb = aut.trans.(!etat) in if mot.[i] = 'a' then eta else etb;
	done;
	aut.final.(!etat);;

accepte aut_1 "aabbbbbababbaa";;
accepte aut_1 "aabbabbbbabba";;

(* Exercice 4 *)

let non_vide aut =
	let vu = Array.make aut.n false in
	vu.(0) <- true;
	for i = 0 to (aut.n)-1 do
		for j = 0 to (aut.n)-1 do
			if vu.(j) then let eta,etb = aut.trans.(j) in (vu.(eta) <- true ; vu.(etb) <- true);
		done;
	done;
	let b = ref false in
	for k = 0 to (aut.n)-1 do
		b := !b || (vu.(k) && aut.final.(k))
	done;
	!b;;

non_vide aut_1;;
non_vide aut_2;;

(* Exercice 6 *)

let bij n m (i,j) = m*i+j;;

let antibij n m k = (k/m,k mod m);;

for i = 0 to 3 do for j = 0 to 4 do print_int (bij 4 5 (i,j)) ; print_string " " done done;;
for k = 0 to 19 do let i,j = antibij 4 5 k in (print_int i ; print_string "," ; print_int j ; print_string " - ") done;;

let produit aut1 aut2 =
	let nprod = aut1.n * aut2.n in
	let finalprod = Array.make nprod false in
	for i = 0 to (aut1.n)-1 do
		for j = 0 to (aut2.n)-1 do
			finalprod.(bij aut1.n aut2.n (i,j)) <- aut1.final.(i) && aut2.final.(j);
		done;
	done;
	let transprod = Array.make nprod (-1,-1) in
	for i = 0 to (aut1.n)-1 do
		for j = 0 to (aut2.n)-1 do
			let ta1,tb1 = aut1.trans.(i) in
			let ta2,tb2 = aut2.trans.(j) in
			transprod.(bij aut1.n aut2.n (i,j)) <- (bij aut1.n aut2.n (ta1,ta2),bij aut1.n aut2.n (tb1,tb2));
		done;
	done;
	{n = nprod ; final = finalprod ; trans = transprod};;

produit aut_1 aut_2;;

(* Exercice 7 *)

type expression = V | Eps | L of char | Prod of expression * expression | Sum of expression * expression | Etoile of expression;;

type autg = {n : int ; final : bool array ; trans : expression array array};;

(* Exercice 11 *)

let rec pow2 = let squ x = x*x in
	function
		| 0 -> 1
		| n when n mod 2 = 0 -> squ (pow2 (n/2))
		| n -> 2*(squ (pow2 (n/2)));;

pow2 10;;
pow2 3;;

let rec psi = function | [] -> 0 | h::t -> (pow2 h) + (psi t);;

psi [1;2];;

let antipsi n =
	let liste = ref [] in